"""
@Project ：Python_Learning 
@File    ：链表.py
@IDE     ：PyCharm 
@Author  ：zhupp
@Date    ：2024/10/16 15:06 
"""


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_head(self, val):
        new_node = ListNode(val, self.head)
        self.head = new_node

    def insert_at_tail(self, val):
        new_node = ListNode(val)
        if not self.head:
            self.head = new_node
            return
        current_node = self.head
        while current_node.next:      # 指向最后一个节点时停下
            current_node = current_node.next
        current_node.next = new_node

    def insert_at_middle(self, pre_node, val):
        if not pre_node:
            return
        new_node = ListNode(val)
        new_node.next = pre_node.next
        pre_node.next = new_node

    def delete(self, key):
        if not self.head:
            return
        if self.head.val == key:
            self.head = self.head.next
            return
        current_node = self.head
        # 当当前节点指向的【下一个】节点不为空且不等于key，则current_node跳向下一个节点
        while current_node.next and current_node.next.val != key:
            current_node = current_node.next
        # 循环结束后会找到等于key值的节点（如果存在）
        if current_node.next:
            current_node.next = current_node.next.next

    def traverse(self):
        current_node = self.head
        while current_node:
            print(current_node.val, end='->')
            current_node = current_node.next
        print("None")


llist = LinkedList()

llist.insert_at_head(1)
llist.insert_at_head(2)
llist.insert_at_tail(3)
llist.insert_at_middle(llist.head, 4)
llist.delete(1)
llist.traverse()


